/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 123
 * Date: 2023-06-07
 * Time: 8:57
 */
public class ListNode {
   static class Node{
       int val;
       Node next = null;

      Node(int val) {
           this.val = val;
       }

   }

   public Node create(){
       Node A = new Node(6) ;
       Node B = new Node(2) ;
       Node C = new Node(8) ;
       A.next = B ;
       B.next = C ;
       C.next = null ;
       return A ;
   }

    public Node partition(Node pHead, int x) {
        if(pHead == null) return null;
        if(pHead.next == null) return pHead ;

        Node littleHead = new Node(-1) ;
        Node bigHead = new Node(-1) ;
        Node ret = pHead ;
        Node retNext = ret.next ;
        while(retNext != null){
            if(ret.val < x){
                addLast(littleHead , ret.val) ;
            }else {
                addLast(bigHead , ret.val) ;
            }
            ret = retNext ;
            retNext = retNext .next ;
        }
        if(ret.val < x){
            addLast(littleHead , ret.val) ;
        }else {
            addLast(bigHead , ret.val) ;
        }
        if(littleHead == null)return bigHead ;
        if(bigHead == null)return littleHead ;

        ret = littleHead ;
        while(ret.next != null){
            ret = ret.next ;
        }
        ret.next = bigHead ;
        return littleHead ;

    }

    public void addLast(Node head , int x){
       Node p = new Node(x) ;
       if(head.val == -1){
           head = p ;
           return ;
       }
       Node ret = head ;
       while(ret.next != null){
           ret = ret.next ;
       }
       ret.next = p ;
       p .next = null ;

    }
}